package leetcode;

/**
 * 买卖股票最佳时机3 ：核心：进行2次股票买卖操作计算最大收益
 */
public class Solution56 {
    class Solution {
        public int maxProfit(int[] prices) {
            if(prices == null || prices.length == 0){
                return 0;
            }
            int n = prices.length;
            //进行数组初始化  创建[][4]数组
            int[][] dp = new int[n][5];
            dp[0][1] = -prices[0];
            dp[0][3] = -prices[0];
            for(int i = 1;i < n;i++){
                //分为四种情况
                //dp[0][0]不操作
                //dp[i][1]第一次持有
                //dp[i][2]第一次不持有
                //dp[i][3]第二次持有
                //dp[i][4]第二次不持有
                dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
                dp[i][2] = Math.max(dp[i-1][2],dp[i][1] + prices[i]);
                dp[i][3] = Math.max(dp[i-1][3],dp[i][2] - prices[i]);
                dp[i][4] = Math.max(dp[i-1][4],dp[i][3] + prices[i]);
            }
            return dp[n-1][4];
        }
    }
}
